import java.util.TreeSet;

/**
 * @author hewei
 * @version 1.0
 * @description: TODO
 * @date 2022/9/13 14:17
 */

public class ExamRoom {

    TreeSet<Integer> set;
    int n;

    public ExamRoom(int n) {
        set = new TreeSet<>();
        this.n = n;
    }

    public int seat() {
        int res = 0;
        if (set.size() != 0) {
            int max = -1;
            int last = -1;
            for (Integer next : set) {
                if (last == -1) {
                    max = next;
                    res = 0;
                } else if (max < (next - last) / 2) {
                    max = (next - last) / 2;
                    res = last + max;
                }
                last = next;
            }
            if (n - 1 - set.last() > max) res = n - 1;
        }
        set.add(res);
        return res;
    }

    public void leave(int p) {
        set.remove(p);
    }
}
